module type FractionSig = sig
  (* A fraction is a rational number p/q, where q != 0.*)
  type t

  (* [make n d] is n/d. Requires d != 0. *)
  val make : int -> int -> t

  val numerator : t -> int
  val denominator : t -> int
  val to_string : t -> string
  val to_float : t -> float

  val add : t -> t -> t
  val mul : t -> t -> t
end

let rec gcd (x:int) (y:int) : int =
  if x = 0 then y
  else if (x < y) then gcd (y - x) x
  else gcd y (x - y)

module Fraction: FractionSig = struct
    type t = int * int

    let rec reduced (x, y) =
      if y < 0
      then reduced (-x, -y)
      else let gcd_n = gcd x y in (x / gcd_n, y / gcd_n)

    let make x y = reduced (x, y)

    let numerator (x, _) = x

    let denominator (_, y) = y

    let to_string (x, y) = string_of_int x ^ "/" ^ string_of_int y

    let to_float (x, y) = float_of_int x /. float_of_int y

    let add (x0, y0) (x1, y1) = reduced (x0 * y1 + x1 * y0, y1 * y0)

    let mul (x0, y0) (x1, y1) = reduced (x0 * x1, y0 * y1)
end

let a = Fraction.make (-2) 4

let b = Fraction.(add a (make 2 3))

let _ = Fraction.to_string b
